#include "quickSort.h"
#include "directSort.h"
//快速排序是在实践中最快的已知排序算法，它的平均运行时间是O(NlogN)。该算法之所以特别快，
//是因为非常精炼已经高度优化的内部循环，快速排序也是一种分治的递归算法。
/*
将数组S排序的基本算法由下列简单的4步组成:
1. 如果S中的元素个数为0或1，则返回
2. 取S中任意元素v，称之为枢纽元
3. 将S中除了v中的其他元素分为两个不相交集S1和S2(小于v的元素和大于v的元素)
4. 执行对S1的排序，然后v，然后对S2的排序

对于枢纽元的选取需要有良好的决策。
1. 一种错误的做法。将第一个元素作为枢纽元，对于非随机的输入，这是一个劣质的分割。
2. 一种安全的做法。随机选取枢纽元。不过随机数的产生是比较昂贵的。
3. 三数中值分割法。使用左端，中间和右端元素中的中值作为枢纽元。

分割策略
1. 将枢纽元和最后一个元素交换使得枢纽元离开要被分割的数据段。
2. 在分割阶段要做的就是把所有小元素移到数组的左边而把所有大元素移动到数组的右边。为此建立两个游标i,j从两侧向中间移动。
i向右移，移过那些比枢纽元小的元素，j向左移，已过那些比枢纽元大的元素，当i和j都停止时，如果i在j的左侧，则将i和j对应的元素
交换。
3. 当i在j的右侧时，此时i对应的元素比枢纽元大，将i对应的元素和枢纽元交换，那么以枢纽元为分界线，分割了两个集合
4. 考虑等于枢纽元的情况。如果i和j的元素等于枢纽元的关键字，那么我们需要让i和j停止。

小数组
对于小数组，快速排序不如插入排序。在快排的递归调用过程中，会不断产生小数组，此时应该使用插入排序。
*/

static void Swap(ElementType *a, ElementType *b)
{
    ElementType tmp = *a;
    *a = *b;
    *b = tmp;
}

//三数中值分割法，找到left, center, right中的中间值，并且将这三个数排序。排序后，我们也不需要担心i或j越界了
static ElementType Median3(ElementType *A, int Left, int Right)
{
    int Center = (Left + Right) / 2;
    if (A[Left] > A[Center])
        Swap(&A[Left], &A[Center]);
    if (A[Left] > A[Right])
        Swap(&A[Left], &A[Right]);
    if (A[Center] > A[Right])
        Swap(&A[Center], &A[Right]);

    //将枢纽元交换到Right-1的位置
    Swap(&A[Center], &A[Right - 1]);
    return A[Right - 1];
}

#define Cutoff (3)

static void QuickSort(ElementType *A, int Left, int Right)
{
    //当数组大小小于Cutoff时进行插入排序
    if (Right - Left >= Cutoff)
    {
        int i, j;
        ElementType Pivot;
        Pivot = Median3(A, Left, Right);
        i = Left, j = Right - 1;
        for (;;)
        {
            //Median3保证在越界之前会跳出循环
            while (A[++i] < Pivot)
            {
            }
            while (A[--j] > Pivot)
            {
            }
            //当两者都停下来后，如果i<j则交换两个元素，否则跳出本次分割策略
            if (i < j)
            {
                Swap(&A[i], &A[j]);
            }
            else
                break;
        }
        //将枢纽元还原到原来的位置，然后对枢纽元两侧的数组进行递归排序
        Swap(&A[i], &A[Right - 1]);
        QuickSort(A, Left, i - 1);
        QuickSort(A, i + 1, Right);
    }
    else
    {
        InsertionSort(A + Left, Right - Left + 1);
    }
}

void Sort(ElementType *A, int N)
{
    QuickSort(A, 0, N - 1);
}

//Select会破坏原有顺序
//和优先级队列类似，不会将数据以顺序形式组织，因此有更好的时间界
//我们将这种算法叫做快速选择。
/*
快速选择的步骤如下:
1. 如果数组大小为1，那么k=1，可以直接返回。如果数组大小为小数组，使用插入排序直接排序后返回。
2. 选取一个枢纽元
3. 将集合基于枢纽元分割为S1和S2
4. 如果k<=S1的大小，那么k一定在S1中，则只需要到S1中选择即可，如果和S1大小相同，那么其就是枢纽元，反之则在S2中。
*/
//
static void Qselect(ElementType *A, int k, int Left, int Right)
{
    //当数组大小小于Cutoff时进行插入排序
    if (Right - Left >= Cutoff)
    {
        int i, j;
        ElementType Pivot;
        Pivot = Median3(A, Left, Right);
        i = Left, j = Right - 1;
        for (;;)
        {
            //Median3保证在越界之前会跳出循环
            while (A[++i] < Pivot)
            {
            }
            while (A[--j] > Pivot)
            {
            }
            //当两者都停下来后，如果i<j则交换两个元素，否则跳出本次分割策略
            if (i < j)
            {
                Swap(&A[i], &A[j]);
            }
            else
                break;
        }
        //将枢纽元还原到原来的位置，然后对枢纽元两侧的数组进行递归选择
        Swap(&A[i], &A[Right - 1]);

        if (k <= i)
            Qselect(A, k, Left, i - 1);
        else if (k > i + 1)
            Qselect(A, k, i + 1, Right);
    }
    else
    {
        InsertionSort(A, Right - Left + 1);
    }
}

void Select(ElementType *A, int k, int N)
{
    Qselect(A, k, 0, N - 1);
}